* Step 1: Bounds WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
active(cons(X1,X2)) -> cons(active(X1),X2)
active(incr(X)) -> incr(active(X))
active(incr(cons(X,XS))) -> mark(cons(s(X),incr(XS)))
active(oddNs()) -> mark(incr(pairNs()))
active(pairNs()) -> mark(cons(0(),incr(oddNs())))
active(s(X)) -> s(active(X))
cons(mark(X1),X2) -> mark(cons(X1,X2))
cons(ok(X1),ok(X2)) -> ok(cons(X1,X2))
incr(mark(X)) -> mark(incr(X))
incr(ok(X)) -> ok(incr(X))
pair(X1,mark(X2)) -> mark(pair(X1,X2))
pair(mark(X1),X2) -> mark(pair(X1,X2))
pair(ok(X1),ok(X2)) -> ok(pair(X1,X2))
proper(0()) -> ok(0())
proper(cons(X1,X2)) -> cons(proper(X1),proper(X2))
proper(incr(X)) -> incr(proper(X))
proper(nil()) -> ok(nil())
proper(oddNs()) -> ok(oddNs())
proper(pairNs()) -> ok(pairNs())
proper(s(X)) -> s(proper(X))
repItems(mark(X)) -> mark(repItems(X))
repItems(ok(X)) -> ok(repItems(X))
s(mark(X)) -> mark(s(X))
s(ok(X)) -> ok(s(X))
tail(mark(X)) -> mark(tail(X))
tail(ok(X)) -> ok(tail(X))
take(X1,mark(X2)) -> mark(take(X1,X2))
take(mark(X1),X2) -> mark(take(X1,X2))
take(ok(X1),ok(X2)) -> ok(take(X1,X2))
top(mark(X)) -> top(proper(X))
top(ok(X)) -> top(active(X))
zip(X1,mark(X2)) -> mark(zip(X1,X2))
zip(mark(X1),X2) -> mark(zip(X1,X2))
zip(ok(X1),ok(X2)) -> ok(zip(X1,X2))
- Signature:
{active/1,cons/2,incr/1,pair/2,proper/1,repItems/1,s/1,tail/1,take/2,top/1,zip/2} / {0/0,mark/1,nil/0
,oddNs/0,ok/1,pairNs/0}
- Obligation:
runtime complexity wrt. defined symbols {active,cons,incr,pair,proper,repItems,s,tail,take,top
,zip} and constructors {0,mark,nil,oddNs,ok,pairNs}
+ Applied Processor:
Bounds {initialAutomaton = perSymbol, enrichment = match}
+ Details:
The problem is match-bounded by 9.
The enriched problem is compatible with follwoing automaton.
0_0() -> 1
0_1() -> 20
0_2() -> 35
0_3() -> 54
0_4() -> 63
0_5() -> 81
0_6() -> 105
active_0(1) -> 2
active_0(5) -> 2
active_0(6) -> 2
active_0(7) -> 2
active_0(8) -> 2
active_0(10) -> 2
active_1(1) -> 30
active_1(5) -> 30
active_1(6) -> 30
active_1(7) -> 30
active_1(8) -> 30
active_1(10) -> 30
active_2(19) -> 32
active_2(20) -> 32
active_2(22) -> 32
active_3(44) -> 43
active_4(34) -> 52
active_4(35) -> 60
active_4(42) -> 60
active_4(58) -> 59
active_5(51) -> 61
active_5(54) -> 68
active_5(80) -> 67
active_6(63) -> 88
active_6(78) -> 72
active_6(86) -> 87
active_7(81) -> 98
active_7(85) -> 89
active_7(110) -> 97
active_8(104) -> 112
active_8(105) -> 116
active_8(113) -> 114
active_9(108) -> 115
cons_0(1,1) -> 3
cons_0(1,5) -> 3
cons_0(1,6) -> 3
cons_0(1,7) -> 3
cons_0(1,8) -> 3
cons_0(1,10) -> 3
cons_0(5,1) -> 3
cons_0(5,5) -> 3
cons_0(5,6) -> 3
cons_0(5,7) -> 3
cons_0(5,8) -> 3
cons_0(5,10) -> 3
cons_0(6,1) -> 3
cons_0(6,5) -> 3
cons_0(6,6) -> 3
cons_0(6,7) -> 3
cons_0(6,8) -> 3
cons_0(6,10) -> 3
cons_0(7,1) -> 3
cons_0(7,5) -> 3
cons_0(7,6) -> 3
cons_0(7,7) -> 3
cons_0(7,8) -> 3
cons_0(7,10) -> 3
cons_0(8,1) -> 3
cons_0(8,5) -> 3
cons_0(8,6) -> 3
cons_0(8,7) -> 3
cons_0(8,8) -> 3
cons_0(8,10) -> 3
cons_0(10,1) -> 3
cons_0(10,5) -> 3
cons_0(10,6) -> 3
cons_0(10,7) -> 3
cons_0(10,8) -> 3
cons_0(10,10) -> 3
cons_1(1,1) -> 23
cons_1(1,5) -> 23
cons_1(1,6) -> 23
cons_1(1,7) -> 23
cons_1(1,8) -> 23
cons_1(1,10) -> 23
cons_1(5,1) -> 23
cons_1(5,5) -> 23
cons_1(5,6) -> 23
cons_1(5,7) -> 23
cons_1(5,8) -> 23
cons_1(5,10) -> 23
cons_1(6,1) -> 23
cons_1(6,5) -> 23
cons_1(6,6) -> 23
cons_1(6,7) -> 23
cons_1(6,8) -> 23
cons_1(6,10) -> 23
cons_1(7,1) -> 23
cons_1(7,5) -> 23
cons_1(7,6) -> 23
cons_1(7,7) -> 23
cons_1(7,8) -> 23
cons_1(7,10) -> 23
cons_1(8,1) -> 23
cons_1(8,5) -> 23
cons_1(8,6) -> 23
cons_1(8,7) -> 23
cons_1(8,8) -> 23
cons_1(8,10) -> 23
cons_1(10,1) -> 23
cons_1(10,5) -> 23
cons_1(10,6) -> 23
cons_1(10,7) -> 23
cons_1(10,8) -> 23
cons_1(10,10) -> 23
cons_1(20,21) -> 18
cons_2(35,36) -> 33
cons_2(38,39) -> 32
cons_3(35,45) -> 44
cons_3(42,45) -> 44
cons_3(46,47) -> 43
cons_3(54,55) -> 53
cons_4(54,57) -> 58
cons_4(60,45) -> 43
cons_4(63,64) -> 62
cons_4(69,70) -> 61
cons_5(63,73) -> 78
cons_5(68,57) -> 59
cons_5(74,75) -> 72
cons_6(81,79) -> 85
cons_6(83,84) -> 82
cons_6(88,73) -> 72
cons_7(91,92) -> 90
cons_7(93,94) -> 87
cons_7(98,79) -> 89
cons_7(104,92) -> 110
cons_8(99,100) -> 97
cons_8(108,111) -> 113
cons_8(112,92) -> 97
cons_9(115,111) -> 114
incr_0(1) -> 4
incr_0(5) -> 4
incr_0(6) -> 4
incr_0(7) -> 4
incr_0(8) -> 4
incr_0(10) -> 4
incr_1(1) -> 24
incr_1(5) -> 24
incr_1(6) -> 24
incr_1(7) -> 24
incr_1(8) -> 24
incr_1(10) -> 24
incr_1(19) -> 18
incr_1(22) -> 21
incr_2(34) -> 33
incr_2(37) -> 36
incr_2(40) -> 32
incr_2(41) -> 39
incr_3(34) -> 44
incr_3(37) -> 45
incr_3(48) -> 43
incr_3(49) -> 47
incr_3(50) -> 55
incr_4(50) -> 57
incr_4(51) -> 58
incr_4(52) -> 43
incr_4(53) -> 56
incr_4(65) -> 64
incr_4(71) -> 70
incr_5(61) -> 59
incr_5(62) -> 66
incr_5(65) -> 73
incr_5(76) -> 75
incr_6(72) -> 67
incr_6(73) -> 84
incr_6(77) -> 79
incr_6(78) -> 80
incr_6(101) -> 95
incr_7(79) -> 92
incr_7(85) -> 86
incr_7(89) -> 87
incr_7(95) -> 94
incr_7(106) -> 102
incr_7(107) -> 109
incr_8(102) -> 100
incr_8(109) -> 111
mark_0(1) -> 5
mark_0(5) -> 5
mark_0(6) -> 5
mark_0(7) -> 5
mark_0(8) -> 5
mark_0(10) -> 5
mark_1(18) -> 2
mark_1(18) -> 30
mark_1(23) -> 3
mark_1(23) -> 23
mark_1(24) -> 4
mark_1(24) -> 24
mark_1(25) -> 9
mark_1(25) -> 25
mark_1(26) -> 12
mark_1(26) -> 26
mark_1(27) -> 13
mark_1(27) -> 27
mark_1(28) -> 14
mark_1(28) -> 28
mark_1(29) -> 15
mark_1(29) -> 29
mark_1(31) -> 17
mark_1(31) -> 31
mark_2(33) -> 32
mark_3(53) -> 52
mark_4(56) -> 43
mark_4(62) -> 61
mark_5(66) -> 59
mark_6(82) -> 67
mark_7(90) -> 87
nil_0() -> 6
nil_1() -> 20
nil_2() -> 42
oddNs_0() -> 7
oddNs_1() -> 22
oddNs_2() -> 37
oddNs_3() -> 50
oddNs_4() -> 65
oddNs_5() -> 77
oddNs_6() -> 107
ok_0(1) -> 8
ok_0(5) -> 8
ok_0(6) -> 8
ok_0(7) -> 8
ok_0(8) -> 8
ok_0(10) -> 8
ok_1(19) -> 11
ok_1(19) -> 30
ok_1(20) -> 11
ok_1(20) -> 30
ok_1(22) -> 11
ok_1(22) -> 30
ok_1(23) -> 3
ok_1(23) -> 23
ok_1(24) -> 4
ok_1(24) -> 24
ok_1(25) -> 9
ok_1(25) -> 25
ok_1(26) -> 12
ok_1(26) -> 26
ok_1(27) -> 13
ok_1(27) -> 27
ok_1(28) -> 14
ok_1(28) -> 28
ok_1(29) -> 15
ok_1(29) -> 29
ok_1(31) -> 17
ok_1(31) -> 31
ok_2(34) -> 40
ok_2(35) -> 38
ok_2(37) -> 41
ok_2(42) -> 38
ok_3(44) -> 32
ok_3(45) -> 39
ok_3(50) -> 49
ok_3(51) -> 48
ok_3(54) -> 46
ok_4(57) -> 47
ok_4(58) -> 43
ok_4(63) -> 69
ok_4(65) -> 71
ok_5(73) -> 70
ok_5(77) -> 76
ok_5(77) -> 101
ok_5(78) -> 61
ok_5(81) -> 74
ok_5(81) -> 96
ok_6(79) -> 75
ok_6(79) -> 95
ok_6(80) -> 59
ok_6(85) -> 72
ok_6(104) -> 93
ok_6(105) -> 103
ok_6(107) -> 106
ok_7(86) -> 67
ok_7(92) -> 94
ok_7(108) -> 99
ok_7(109) -> 102
ok_7(110) -> 87
ok_8(111) -> 100
ok_8(113) -> 97
pair_0(1,1) -> 9
pair_0(1,5) -> 9
pair_0(1,6) -> 9
pair_0(1,7) -> 9
pair_0(1,8) -> 9
pair_0(1,10) -> 9
pair_0(5,1) -> 9
pair_0(5,5) -> 9
pair_0(5,6) -> 9
pair_0(5,7) -> 9
pair_0(5,8) -> 9
pair_0(5,10) -> 9
pair_0(6,1) -> 9
pair_0(6,5) -> 9
pair_0(6,6) -> 9
pair_0(6,7) -> 9
pair_0(6,8) -> 9
pair_0(6,10) -> 9
pair_0(7,1) -> 9
pair_0(7,5) -> 9
pair_0(7,6) -> 9
pair_0(7,7) -> 9
pair_0(7,8) -> 9
pair_0(7,10) -> 9
pair_0(8,1) -> 9
pair_0(8,5) -> 9
pair_0(8,6) -> 9
pair_0(8,7) -> 9
pair_0(8,8) -> 9
pair_0(8,10) -> 9
pair_0(10,1) -> 9
pair_0(10,5) -> 9
pair_0(10,6) -> 9
pair_0(10,7) -> 9
pair_0(10,8) -> 9
pair_0(10,10) -> 9
pair_1(1,1) -> 25
pair_1(1,5) -> 25
pair_1(1,6) -> 25
pair_1(1,7) -> 25
pair_1(1,8) -> 25
pair_1(1,10) -> 25
pair_1(5,1) -> 25
pair_1(5,5) -> 25
pair_1(5,6) -> 25
pair_1(5,7) -> 25
pair_1(5,8) -> 25
pair_1(5,10) -> 25
pair_1(6,1) -> 25
pair_1(6,5) -> 25
pair_1(6,6) -> 25
pair_1(6,7) -> 25
pair_1(6,8) -> 25
pair_1(6,10) -> 25
pair_1(7,1) -> 25
pair_1(7,5) -> 25
pair_1(7,6) -> 25
pair_1(7,7) -> 25
pair_1(7,8) -> 25
pair_1(7,10) -> 25
pair_1(8,1) -> 25
pair_1(8,5) -> 25
pair_1(8,6) -> 25
pair_1(8,7) -> 25
pair_1(8,8) -> 25
pair_1(8,10) -> 25
pair_1(10,1) -> 25
pair_1(10,5) -> 25
pair_1(10,6) -> 25
pair_1(10,7) -> 25
pair_1(10,8) -> 25
pair_1(10,10) -> 25
pairNs_0() -> 10
pairNs_1() -> 19
pairNs_2() -> 34
pairNs_3() -> 51
proper_0(1) -> 11
proper_0(5) -> 11
proper_0(6) -> 11
proper_0(7) -> 11
proper_0(8) -> 11
proper_0(10) -> 11
proper_1(1) -> 30
proper_1(5) -> 30
proper_1(6) -> 30
proper_1(7) -> 30
proper_1(8) -> 30
proper_1(10) -> 30
proper_2(18) -> 32
proper_2(19) -> 40
proper_2(20) -> 38
proper_2(21) -> 39
proper_2(22) -> 41
proper_3(33) -> 43
proper_3(34) -> 48
proper_3(35) -> 46
proper_3(36) -> 47
proper_3(37) -> 49
proper_4(50) -> 71
proper_4(54) -> 69
proper_4(55) -> 70
proper_4(56) -> 59
proper_5(53) -> 61
proper_5(63) -> 74
proper_5(64) -> 75
proper_5(65) -> 76
proper_5(66) -> 67
proper_6(62) -> 72
proper_6(65) -> 101
proper_6(82) -> 87
proper_7(63) -> 96
proper_7(73) -> 95
proper_7(77) -> 106
proper_7(83) -> 93
proper_7(84) -> 94
proper_7(90) -> 97
proper_8(79) -> 102
proper_8(81) -> 103
proper_8(91) -> 99
proper_8(92) -> 100
repItems_0(1) -> 12
repItems_0(5) -> 12
repItems_0(6) -> 12
repItems_0(7) -> 12
repItems_0(8) -> 12
repItems_0(10) -> 12
repItems_1(1) -> 26
repItems_1(5) -> 26
repItems_1(6) -> 26
repItems_1(7) -> 26
repItems_1(8) -> 26
repItems_1(10) -> 26
s_0(1) -> 13
s_0(5) -> 13
s_0(6) -> 13
s_0(7) -> 13
s_0(8) -> 13
s_0(10) -> 13
s_1(1) -> 27
s_1(5) -> 27
s_1(6) -> 27
s_1(7) -> 27
s_1(8) -> 27
s_1(10) -> 27
s_6(63) -> 83
s_6(81) -> 104
s_7(81) -> 91
s_7(96) -> 93
s_7(98) -> 112
s_7(105) -> 108
s_8(103) -> 99
s_8(116) -> 115
tail_0(1) -> 14
tail_0(5) -> 14
tail_0(6) -> 14
tail_0(7) -> 14
tail_0(8) -> 14
tail_0(10) -> 14
tail_1(1) -> 28
tail_1(5) -> 28
tail_1(6) -> 28
tail_1(7) -> 28
tail_1(8) -> 28
tail_1(10) -> 28
take_0(1,1) -> 15
take_0(1,5) -> 15
take_0(1,6) -> 15
take_0(1,7) -> 15
take_0(1,8) -> 15
take_0(1,10) -> 15
take_0(5,1) -> 15
take_0(5,5) -> 15
take_0(5,6) -> 15
take_0(5,7) -> 15
take_0(5,8) -> 15
take_0(5,10) -> 15
take_0(6,1) -> 15
take_0(6,5) -> 15
take_0(6,6) -> 15
take_0(6,7) -> 15
take_0(6,8) -> 15
take_0(6,10) -> 15
take_0(7,1) -> 15
take_0(7,5) -> 15
take_0(7,6) -> 15
take_0(7,7) -> 15
take_0(7,8) -> 15
take_0(7,10) -> 15
take_0(8,1) -> 15
take_0(8,5) -> 15
take_0(8,6) -> 15
take_0(8,7) -> 15
take_0(8,8) -> 15
take_0(8,10) -> 15
take_0(10,1) -> 15
take_0(10,5) -> 15
take_0(10,6) -> 15
take_0(10,7) -> 15
take_0(10,8) -> 15
take_0(10,10) -> 15
take_1(1,1) -> 29
take_1(1,5) -> 29
take_1(1,6) -> 29
take_1(1,7) -> 29
take_1(1,8) -> 29
take_1(1,10) -> 29
take_1(5,1) -> 29
take_1(5,5) -> 29
take_1(5,6) -> 29
take_1(5,7) -> 29
take_1(5,8) -> 29
take_1(5,10) -> 29
take_1(6,1) -> 29
take_1(6,5) -> 29
take_1(6,6) -> 29
take_1(6,7) -> 29
take_1(6,8) -> 29
take_1(6,10) -> 29
take_1(7,1) -> 29
take_1(7,5) -> 29
take_1(7,6) -> 29
take_1(7,7) -> 29
take_1(7,8) -> 29
take_1(7,10) -> 29
take_1(8,1) -> 29
take_1(8,5) -> 29
take_1(8,6) -> 29
take_1(8,7) -> 29
take_1(8,8) -> 29
take_1(8,10) -> 29
take_1(10,1) -> 29
take_1(10,5) -> 29
take_1(10,6) -> 29
take_1(10,7) -> 29
take_1(10,8) -> 29
take_1(10,10) -> 29
top_0(1) -> 16
top_0(5) -> 16
top_0(6) -> 16
top_0(7) -> 16
top_0(8) -> 16
top_0(10) -> 16
top_1(30) -> 16
top_2(32) -> 16
top_3(43) -> 16
top_4(59) -> 16
top_5(67) -> 16
top_6(87) -> 16
top_7(97) -> 16
top_8(114) -> 16
zip_0(1,1) -> 17
zip_0(1,5) -> 17
zip_0(1,6) -> 17
zip_0(1,7) -> 17
zip_0(1,8) -> 17
zip_0(1,10) -> 17
zip_0(5,1) -> 17
zip_0(5,5) -> 17
zip_0(5,6) -> 17
zip_0(5,7) -> 17
zip_0(5,8) -> 17
zip_0(5,10) -> 17
zip_0(6,1) -> 17
zip_0(6,5) -> 17
zip_0(6,6) -> 17
zip_0(6,7) -> 17
zip_0(6,8) -> 17
zip_0(6,10) -> 17
zip_0(7,1) -> 17
zip_0(7,5) -> 17
zip_0(7,6) -> 17
zip_0(7,7) -> 17
zip_0(7,8) -> 17
zip_0(7,10) -> 17
zip_0(8,1) -> 17
zip_0(8,5) -> 17
zip_0(8,6) -> 17
zip_0(8,7) -> 17
zip_0(8,8) -> 17
zip_0(8,10) -> 17
zip_0(10,1) -> 17
zip_0(10,5) -> 17
zip_0(10,6) -> 17
zip_0(10,7) -> 17
zip_0(10,8) -> 17
zip_0(10,10) -> 17
zip_1(1,1) -> 31
zip_1(1,5) -> 31
zip_1(1,6) -> 31
zip_1(1,7) -> 31
zip_1(1,8) -> 31
zip_1(1,10) -> 31
zip_1(5,1) -> 31
zip_1(5,5) -> 31
zip_1(5,6) -> 31
zip_1(5,7) -> 31
zip_1(5,8) -> 31
zip_1(5,10) -> 31
zip_1(6,1) -> 31
zip_1(6,5) -> 31
zip_1(6,6) -> 31
zip_1(6,7) -> 31
zip_1(6,8) -> 31
zip_1(6,10) -> 31
zip_1(7,1) -> 31
zip_1(7,5) -> 31
zip_1(7,6) -> 31
zip_1(7,7) -> 31
zip_1(7,8) -> 31
zip_1(7,10) -> 31
zip_1(8,1) -> 31
zip_1(8,5) -> 31
zip_1(8,6) -> 31
zip_1(8,7) -> 31
zip_1(8,8) -> 31
zip_1(8,10) -> 31
zip_1(10,1) -> 31
zip_1(10,5) -> 31
zip_1(10,6) -> 31
zip_1(10,7) -> 31
zip_1(10,8) -> 31
zip_1(10,10) -> 31
* Step 2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
active(cons(X1,X2)) -> cons(active(X1),X2)
active(incr(X)) -> incr(active(X))
active(incr(cons(X,XS))) -> mark(cons(s(X),incr(XS)))
active(oddNs()) -> mark(incr(pairNs()))
active(pairNs()) -> mark(cons(0(),incr(oddNs())))
active(s(X)) -> s(active(X))
cons(mark(X1),X2) -> mark(cons(X1,X2))
cons(ok(X1),ok(X2)) -> ok(cons(X1,X2))
incr(mark(X)) -> mark(incr(X))
incr(ok(X)) -> ok(incr(X))
pair(X1,mark(X2)) -> mark(pair(X1,X2))
pair(mark(X1),X2) -> mark(pair(X1,X2))
pair(ok(X1),ok(X2)) -> ok(pair(X1,X2))
proper(0()) -> ok(0())
proper(cons(X1,X2)) -> cons(proper(X1),proper(X2))
proper(incr(X)) -> incr(proper(X))
proper(nil()) -> ok(nil())
proper(oddNs()) -> ok(oddNs())
proper(pairNs()) -> ok(pairNs())
proper(s(X)) -> s(proper(X))
repItems(mark(X)) -> mark(repItems(X))
repItems(ok(X)) -> ok(repItems(X))
s(mark(X)) -> mark(s(X))
s(ok(X)) -> ok(s(X))
tail(mark(X)) -> mark(tail(X))
tail(ok(X)) -> ok(tail(X))
take(X1,mark(X2)) -> mark(take(X1,X2))
take(mark(X1),X2) -> mark(take(X1,X2))
take(ok(X1),ok(X2)) -> ok(take(X1,X2))
top(mark(X)) -> top(proper(X))
top(ok(X)) -> top(active(X))
zip(X1,mark(X2)) -> mark(zip(X1,X2))
zip(mark(X1),X2) -> mark(zip(X1,X2))
zip(ok(X1),ok(X2)) -> ok(zip(X1,X2))
- Signature:
{active/1,cons/2,incr/1,pair/2,proper/1,repItems/1,s/1,tail/1,take/2,top/1,zip/2} / {0/0,mark/1,nil/0
,oddNs/0,ok/1,pairNs/0}
- Obligation:
runtime complexity wrt. defined symbols {active,cons,incr,pair,proper,repItems,s,tail,take,top
,zip} and constructors {0,mark,nil,oddNs,ok,pairNs}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))